package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/longest-univalue-path/'>最长同值路径(Longest Univalue Path)</a>
 *
 * @author c2b
 * @since 2023/11/21 17:16
 */
public class LC0687 {

    static class Solution {
        int res = 0;

        public int longestUnivaluePath(TreeNode root) {
            dfs(root);
            return res;
        }

        private int dfs(TreeNode node) {
            if (node == null) {
                return 0;
            }
            // 当前节点不计入结果
            int left = 0;
            int right = 0;
            if (node.left != null && node.val == node.left.val) {
                left = dfs(node.left) + 1;
            }
            if (node.right != null && node.val == node.right.val) {
                right = dfs(node.right) + 1;
            }
            res = Math.max(res, left + right);
            return Math.max(left, right);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(5);
        root1.left = new TreeNode(4);
        root1.right = new TreeNode(5);
        root1.left.left = new TreeNode(1);
        root1.left.right = new TreeNode(1);
        root1.right.right = new TreeNode(5);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(4);
        root2.right = new TreeNode(5);
        root2.left.left = new TreeNode(4);
        root2.left.right = new TreeNode(4);
        root2.right.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println(solution.longestUnivaluePath(root1));
        System.out.println(solution.longestUnivaluePath(root2));
    }
}
